<?php


//Definition for a Node.
class Node {
    public $val;
    public $left;
    public $right;
    public $next;
      function __construct($val = 0) {
          $this->val = $val;
          $this->left = null;
          $this->right = null;
          $this->next = null;
      }
}

class nextNode {
    public $map = [];
    /**
     * @param Node $root
     * @return Node
     */
    public function connect($root) {
        if($root == null){
            return null;
        }
        $pre = $root;
        $curr = null;

        while($pre->left != null){
            $curr = $pre;
            while($curr != null){
                $curr->left->next = $curr->right;
                if($curr->next != null){
                    $curr->right->next = $curr->next->left;
                }
                // 继续下一个节点
                $curr = $curr->next;
            }
            // 继续下一层
            $pre = $pre->left;
        }
        return $root;
    }

    public function connects($root)
    {
        $this->dfs($root,null);
        return $root;
    }

    public function dfs($curr,$next)
    {
        if($curr == null){
            return ;
        }

        $curr->next = $next;
        $this->dfs($curr->left,$curr->right);
        $this->dfs($curr->right,$curr->next == null ? '#' : $curr->next->left);
    }

    public function connect1($root)
    {
        if($root == null) return $root;

        $queue = new SplQueue();
        $queue->enqueue($root);

        while($count = $queue->count()){
            // 遍历当前层的所有节点，前一个节点指向后一个节点（最后一个无需处理）
            for($i =0;$i<$count;++$i){
                $node = $queue->dequeue();
                // not the last one
                if($i < $count -1) $node->next = $queue->bottom();

                // 添加下一层的所有节点
                if($node->left != null) $queue->enqueue($node->left);;
                if($node->right != null) $queue->enqueue($node->right);;
            }
        }
    }
    public function connect2($root)
    {
        if($root == null) return $root;

        if($root->left != null){
            // 左子节点指向右子节点
            $root->left->next = $root->right;
            // 右子节点指向同层下一个节点的左子节点
            if($root->next !== null) $root->right->next = $root->next->left;
        }

        $this->connect2($root->left);
        $this->connect2($root->right);
        return $root;
    }

}




$node1 = new Node(1);
$node2 = new Node(2);
$node3 = new Node(3);
$node4 = new Node(4);
$node5 = new Node(5);
$node6 = new Node(6);
$node7 = new Node(7);
$node1->next = null;
$node1->left = $node2;
$node1->right = $node3;
$node2->left = $node4;
$node2->right = $node5;
$node2->next = null;
$node3->left = $node6;
$node3->right = $node7;
$node3->next = null;

$se= (json_encode($node1));
$unse = json_decode($se);
var_dump($se);
var_dump($unse);die;

$nodes = new nextNode();
$root = [1,2,3,4,5,6,7];
$res = $nodes->connect1($node1);
var_export($res);
